// javascript-astar 0.4.1
// http://github.com/bgrins/javascript-astar
// Freely distributable under the MIT License.
// Implements the astar search algorithm in javascript using a Binary Heap.
// Includes Binary Heap (with modifications) from Marijn Haverbeke.
// http://eloquentjavascript.net/appendix2.html

function pathTo(node: GridNode): GridNode[] {
    var curr = node;
    var path = [];
    while (curr.parent) {
        path.unshift(curr);
        curr = curr.parent;
    }
    return path;
}

function getHeap() {
    return new BinaryHeap(function (node: GridNode) {
        return node.f;
    });
}

class Astar {

    /**
    * Perform an A* Search on a graph given a start and end node.
    * @param {AstarGraph} graph
    * @param {GridNode} start
    * @param {GridNode} end
    * @param {Object} [options]
    * @param {bool} [options.closest] Specifies whether to return the
               path to the closest node if the target is unreachable.
    * @param {Function} [options.heuristic] Heuristic function (see
    *          astar.heuristics).
    */
    public static search(graph: AstarGraph, start: GridNode, end: GridNode, options) {
        graph.cleanDirty();
        options = options || {};
        var heuristic = options.heuristic || heuristics.manhattan;
        var closest = options.closest || false;

        var openHeap = getHeap();
        var closestNode = start; // set the start node to be the closest if required

        start.h = heuristic(start, end);
        graph.markDirty(start);

        openHeap.push(start);

        while (openHeap.size() > 0) {

            // Grab the lowest f(x) to process next.  Heap keeps this sorted for us.
            var currentNode = openHeap.pop();

            // End case -- result has been found, return the traced path.
            // if (currentNode === end) {
            //   return pathTo(currentNode);
            // }
            if (currentNode.x == end.x && currentNode.y == end.y) {
                return pathTo(currentNode);
            }

            // Normal case -- move currentNode from open to closed, process each of its neighbors.
            currentNode.closed = true;

            // Find all neighbors for the current node.
            var neighbors = graph.neighbors(currentNode);

            for (var i = 0, il = neighbors.length; i < il; ++i) {
                var neighbor = neighbors[i];

                if (neighbor.closed || neighbor.isWall()) {
                    // Not a valid node to process, skip to next neighbor.
                    continue;
                }

                // The g score is the shortest distance from start to current node.
                // We need to check if the path we have arrived at this neighbor is the shortest one we have seen yet.
                var gScore = currentNode.g + neighbor.getCost(currentNode);
                var beenVisited = neighbor.visited;

                if (!beenVisited || gScore < neighbor.g) {

                    // Found an optimal (so far) path to this node.  Take score for node to see how good it is.
                    neighbor.visited = true;
                    neighbor.parent = currentNode;
                    neighbor.h = neighbor.h || heuristic(neighbor, end);
                    neighbor.g = gScore;
                    neighbor.f = neighbor.g + neighbor.h;
                    graph.markDirty(neighbor);
                    if (closest) {
                        // If the neighbour is closer than the current closestNode or if it's equally close but has
                        // a cheaper path than the current closest node then it becomes the closest node
                        if (neighbor.h < closestNode.h || (neighbor.h === closestNode.h && neighbor.g < closestNode.g)) {
                            closestNode = neighbor;
                        }
                    }

                    if (!beenVisited) {
                        // Pushing to heap will put it in proper place based on the 'f' value.
                        openHeap.push(neighbor);
                    } else {
                        // Already seen the node, but since it has been rescored we need to reorder it in the heap
                        openHeap.rescoreElement(neighbor);
                    }
                }
            }
        }

        if (closest) {
            return pathTo(closestNode);
        }

        // No result was found - empty array signifies failure to find path.
        return [];
    }

    public static cleanNode(node) {
        node.f = 0;
        node.g = 0;
        node.h = 0;
        node.visited = false;
        node.closed = false;
        node.parent = null;
    }
}

// See list of heuristics: http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html
class heuristics {
    public static manhattan(pos0, pos1) {
        var d1 = Math.abs(pos1.x - pos0.x);
        var d2 = Math.abs(pos1.y - pos0.y);
        return d1 + d2;
    }

    public static diagonal(pos0, pos1) {
        var D = 1;
        var D2 = Math.sqrt(2);
        var d1 = Math.abs(pos1.x - pos0.x);
        var d2 = Math.abs(pos1.y - pos0.y);
        return (D * (d1 + d2)) + ((D2 - (2 * D)) * Math.min(d1, d2));
    }
};

class AstarGraph {

    nodes: GridNode[];
    diagonal: boolean = true;
    grid: GridNode[][];
    dirtyNodes: GridNode[];

    /**
       * A graph memory structure
       * @param {Array} gridIn 2D array of input weights
       * @param {Object} [options]
       * @param {bool} [options.diagonal] Specifies whether diagonal moves are allowed
       */
    constructor(gridIn, options) {
        options = options || {};
        this.diagonal = !!options.diagonal;
        this.init(gridIn);
    }

    public init(gridIn) {
        if (this.nodes == null) {
            this.nodes = []
        }
        this.grid = [];
        for (var x = 0; x < gridIn.length; x++) {
            this.grid[x] = [];
            for (var y = 0, row = gridIn[x]; y < row.length; y++) {
                let index = x * row.length + y;
                let node: GridNode = null;
                if (index < this.nodes.length) {
                    node = this.nodes[index];
                    node.x = x;
                    node.y = y;
                    node.weight = row[y];
                }
                else {
                    node = new GridNode(x, y, row[y]);
                    this.nodes.push(node);
                }
                this.grid[x][y] = node;
            }
        }
        this.dirtyNodes = [];
        for (var i = 0; i < this.nodes.length; i++) {
            Astar.cleanNode(this.nodes[i]);
        }
    };

    public cleanDirty() {
        for (var i = 0; i < this.dirtyNodes.length; i++) {
            Astar.cleanNode(this.dirtyNodes[i]);
        }
        this.dirtyNodes = [];
    };

    public markDirty(node) {
        this.dirtyNodes.push(node);
    };

    public static ExtCheckCanWalk: (x, y: number) => boolean = (x: number, y: number): boolean => {
        return true
        // if (MainPlayer.Self.CurGridPos.x == x && MainPlayer.Self.CurGridPos.y == y) {
        //   return false
        // }
        // let ret = true
        // ForeachEServantTypeNoBenYuan((st: EServantType): boolean => {
        //   let p = MainPlayer.Self.GetGhost(st)
        //   if (p != null) {
        //     if (p.CurGridPos.x == x && p.CurGridPos.y == y) {
        //       ret = false
        //       return false
        //     }
        //   }
        //   return true
        // })
        // return ret
    }

    public neighbors(node) {
        var ret = [];
        var x = node.x;
        var y = node.y;
        var grid = this.grid;

        // West
        if (grid[x - 1] && grid[x - 1][y] && AstarGraph.ExtCheckCanWalk(x - 1, y)) {
            ret.push(grid[x - 1][y]);
        }

        // East
        if (grid[x + 1] && grid[x + 1][y] && AstarGraph.ExtCheckCanWalk(x + 1, y)) {
            ret.push(grid[x + 1][y]);
        }

        // South
        if (grid[x] && grid[x][y - 1] && AstarGraph.ExtCheckCanWalk(x, y - 1)) {
            ret.push(grid[x][y - 1]);
        }

        // North
        if (grid[x] && grid[x][y + 1] && AstarGraph.ExtCheckCanWalk(x, y + 1)) {
            ret.push(grid[x][y + 1]);
        }

        if (this.diagonal) {
            // Southwest
            if (grid[x - 1] && grid[x - 1][y - 1] && AstarGraph.ExtCheckCanWalk(x - 1, y - 1)) {
                ret.push(grid[x - 1][y - 1]);
            }

            // Southeast
            if (grid[x + 1] && grid[x + 1][y - 1] && AstarGraph.ExtCheckCanWalk(x + 1, y - 1)) {
                ret.push(grid[x + 1][y - 1]);
            }

            // Northwest
            if (grid[x - 1] && grid[x - 1][y + 1] && AstarGraph.ExtCheckCanWalk(x - 1, y + 1)) {
                ret.push(grid[x - 1][y + 1]);
            }

            // Northeast
            if (grid[x + 1] && grid[x + 1][y + 1] && AstarGraph.ExtCheckCanWalk(x + 1, y + 1)) {
                ret.push(grid[x + 1][y + 1]);
            }
        }

        return ret;
    };

    // public toString() {
    //   var graphString = [];
    //   var nodes = this.grid;
    //   for (var x = 0; x < nodes.length; x++) {
    //     var rowDebug = [];
    //     var row = nodes[x];
    //     for (var y = 0; y < row.length; y++) {
    //       rowDebug.push(row[y].weight);
    //     }
    //     graphString.push(rowDebug.join(" "));
    //   }
    //   return graphString.join("\n");
    // };
}

class GridNode {

    public x: number = 0;
    public y: number = 0;
    public weight: number = 0;
    public h: number = 0;
    public g: number = 0;
    public f: number = 0;
    public closed: boolean = false;
    public parent: GridNode = null;

    constructor(x, y, weight) {
        this.x = x;
        this.y = y;
        this.weight = weight;
    }

    public toString() {
        return "[" + this.x + " " + this.y + "]";
    };

    public getCost(fromNeighbor) {
        // Take diagonal weight into consideration.
        if (fromNeighbor && fromNeighbor.x != this.x && fromNeighbor.y != this.y) {
            return this.weight * 1.41421;
        }
        return this.weight;
    };

    public isWall() {
        return this.weight === 0;
    };
}

class BinaryHeap {

    public content: GridNode[];
    public scoreFunction: (node: GridNode) => number;

    constructor(scoreFunction: (node: GridNode) => number) {
        this.content = [];
        this.scoreFunction = scoreFunction;
    }

    public push(element) {
        // Add the new element to the end of the array.
        this.content.push(element);

        // Allow it to sink down.
        this.sinkDown(this.content.length - 1);
    }

    public pop() {
        // Store the first element so we can return it later.
        var result = this.content[0];
        // Get the element at the end of the array.
        var end = this.content.pop();
        // If there are any elements left, put the end element at the
        // start, and let it bubble up.
        if (this.content.length > 0) {
            this.content[0] = end;
            this.bubbleUp(0);
        }
        return result;
    }

    public remove(node) {
        var i = this.content.indexOf(node);

        // When it is found, the process seen in 'pop' is repeated
        // to fill up the hole.
        var end = this.content.pop();

        if (i !== this.content.length - 1) {
            this.content[i] = end;

            if (this.scoreFunction(end) < this.scoreFunction(node)) {
                this.sinkDown(i);
            } else {
                this.bubbleUp(i);
            }
        }
    }

    public size() {
        return this.content.length;
    }

    public rescoreElement(node) {
        this.sinkDown(this.content.indexOf(node));
    }

    public sinkDown(n) {
        // Fetch the element that has to be sunk.
        var element = this.content[n];

        // When at 0, an element can not sink any further.
        while (n > 0) {

            // Compute the parent element's index, and fetch it.
            var parentN = ((n + 1) >> 1) - 1;
            var parent = this.content[parentN];
            // Swap the elements if the parent is greater.
            if (this.scoreFunction(element) < this.scoreFunction(parent)) {
                this.content[parentN] = element;
                this.content[n] = parent;
                // Update 'n' to continue at the new position.
                n = parentN;
            }
            // Found a parent that is less, no need to sink any further.
            else {
                break;
            }
        }
    }

    public bubbleUp(n) {
        // Look up the target element and its score.
        var length = this.content.length;
        var element = this.content[n];
        var elemScore = this.scoreFunction(element);

        while (true) {
            // Compute the indices of the child elements.
            var child2N = (n + 1) << 1;
            var child1N = child2N - 1;
            // This is used to store the new position of the element, if any.
            var swap = null;
            var child1Score;
            // If the first child exists (is inside the array)...
            if (child1N < length) {
                // Look it up and compute its score.
                var child1 = this.content[child1N];
                child1Score = this.scoreFunction(child1);

                // If the score is less than our element's, we need to swap.
                if (child1Score < elemScore) {
                    swap = child1N;
                }
            }

            // Do the same checks for the other child.
            if (child2N < length) {
                var child2 = this.content[child2N];
                var child2Score = this.scoreFunction(child2);
                if (child2Score < (swap === null ? elemScore : child1Score)) {
                    swap = child2N;
                }
            }

            // If the element needs to be moved, swap it, and continue.
            if (swap !== null) {
                this.content[n] = this.content[swap];
                this.content[swap] = element;
                n = swap;
            }
            // Otherwise, we are done.
            else {
                break;
            }
        }
    }
}